第一章 概论    自测题                                                         

一、填空题

1.  数据结构是一门研究非数值计算的程序设计问题中计算机的                以及它们之间的        和运算等的学科。

2. 数据结构被形式地定义为（D, R），其中D是          的有限集合，R是D上的         有限集合。

3. 数据结构包括数据的                 、数据的            和数据的               这三个方面的内容。

4. 数据结构按逻辑结构可分为两大类，它们分别是               和                     。

5. 线性结构中元素之间存在            关系，树形结构中元素之间存在          关系，图形结构中元素之间存在                   关系。

6． 在线性结构中，第一个结点     前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点        后续结点，其余每个结点有且只有1个后续结点。

7. 在树形结构中，树根结点没有         结点，其余每个结点有且只有        个前驱结点；叶子结点没有         结点，其余每个结点的后续结点数可以                    。

8. 一个算法的效率可分为            效率和                 效率。

二、单项选择题

（     ）1. 非线性结构是数据元素之间存在一种：
              A）一对多关系          B）多对多关系          C）多对一关系          D）一对一关系

（     ）2. 数据结构中，与所使用的计算机无关的是数据的        结构；
              A) 存储          B) 物理          C) 逻辑          D) 物理和存储

（     ）3. 算法分析的两个主要方面是：
              A) 空间复杂性和时间复杂性          B) 正确性和简明性          C) 可读性和文档性          D) 数据复杂性和程序复杂性

（     ）4. 计算机算法必须具备输入、输出和       等5个特性。
              A) 可行性、可移植性和可扩充性          B) 可行性、确定性和有穷性  

              C) 确定性、有穷性和稳定性               D) 易读性、稳定性和安全性

三、简答题

1.数据结构和数据类型两个概念之间有区别吗？

2. 简述线性结构与非线性结构的不同点。

四、分析下面各程序段的时间复杂度

五、设有数据逻辑结构S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？

1.   D={d1,d2,d3,d4}          R={(d1,d2),(d2,d3),(d3,d4) }